04 Consistency

一致性

一致性模型

只有一个服务器。发送消息时发送到服务器上；读取时也从服务器读取。不会出现操作重排。

问题为

• 响应时间长
• 读取慢
• 不支持离线
• 无法处理故障

现实的系统会复制数据，用户、用户设备和服务器都会存储副本。在这种情况下，发送消息会带来不一致。

一般的设计是，读取时只读取本地副本，并定期同步；只同步部分服务器，同步操作而不是数据，使用过滤+追加方式更新。

但这种设计可以导致客户端重排。

最终一致性

所有服务器最终都会获得所有更新，且持有相同更新的服务器有相同的数据内容。对具体的读写方式没有限制。

具体实现为

• 读：直接从本地副本读取
• 写：写入到本地副本并写回。同步时传播到所有服务器

同步时，需要交换不同服务器的数据内容，需要对不同的内容进行排序。不同服务器都需要将操作记录在log中，然后在log中排序。排序后，可能需要重写内容。

考虑到时钟，需要引入nodeid（服务器id）作为额外的排序手段。

• (time, id)：全局一致性更好，但可能因为时钟偏差短暂违背因果顺序，用户体验差
• (id, time)：全局一致性较差，但每个节点严格有序，用户体验较好

实际设计需要权衡。

强一致性

从开发者角度，强一致性代表只有一个副本，一切都串行执行。

严格一致性

按发出时间排序，实际无法实现。

线性一致性

线性一致性是实际可以实现的最强一致性模型。这种方式需要单写入者原则，只允许一个线程读写，将写入顺序传播到其它进程。这种设计需要主服务器使用序列号。

这种设计比最集中实现可能更低效，还会有可靠性问题。

时钟

这里的时钟都只用于实现最终一致性。

Lamport时钟

这是一种逻辑性的时钟。在同一个节点上，lamport给出的结果遵循时间顺序；此外，结果遵循因果关系。

实现：

• 每个服务器包含时钟T
• 随真实时间流逝递增，或在事件发生时递增
• 如果获取另一个服务器的时间t，则T=max(t+1, T)

可能出现不一致，但是后续会回滚。

向量时钟

向量时钟是对lamport时钟的增强。

每个服务器维护一个向量时钟，维度等于服务器数。本地时间发生时，递增自己的向量分量。进程发送消息时，先递增自己，然后发送整个向量。接受时，将每个分量和收到的对比取最大值，并递增自己的分量。如果所有v分量都（相对的）小于w分量，则v小于w。